//
// Created by fh on 2021/7/7.
//

#include "StringMatch.h"

/* 求 char* 字符串长度 */
int StringLength(char *string) {
    int length = 0;
    char *p = string;
    while (*p != '\0') {
        p++;
        length++;
    }
    return length;
}

/* 暴力匹配算法:BF算法 */
int StringMatchBruteForce(char sourceStr[],int sourceStrLength,char targetStr[],int targetStrLength) {
    int index = -1;
    int compareTime = sourceStrLength - targetStrLength + 1;
    for (int i = 0; i < compareTime; ++i) {
        int sameLength = 0;
        for (int j = 0; j < targetStrLength; ++j) {
            if (targetStr[j] == sourceStr[i+j]) {
                sameLength++;
            } else {
                break;
            }
        }
        if (sameLength == targetStrLength) {
            index = i;
            break;
        }
    }
    return index;
}

/* BM算法坏字符部分 */
int StringMatchBoyerMooreBadCharacter(char sourceStr[],int sourceStrLength,char targetStr[],int targetStrLength) {
    int index = -1;
    // 坏字符规则
    // 辅助数组(记录坏字符在模式串中出现的位置):下标是 字符的int值，值是 这个字符在模式字符串中的下标
    int *asciiArr = (int *) malloc(sizeof(int) * 256);
    for (int i = 0; i < 256; ++i) {
        asciiArr[i] = -1;
    }
    for (int i = 0; i < targetStrLength; ++i) {
        int index = (int)targetStr[i];
        asciiArr[index] = i;
    }
    int i = 0;
    while (i <= sourceStrLength - targetStrLength) {
        int sameLength = 0;
        for (int j = targetStrLength - 1; j >= 0; --j) {
            if (targetStr[j] != sourceStr[i+j]) {
                int ci = (int)sourceStr[i+j];
                if (asciiArr[ci] != -1) {
                    // 移动 j - asciiArr[ci]
                    i = i + j - asciiArr[ci];
                } else {
                    // 移动 targetStrLength
                    i = i + targetStrLength;
                }
                break;
            } else {
                sameLength++;
            }
        }
        if (sameLength == targetStrLength) {
            // 找到了
            index = i;
            break;
        }
    }
    return index;
}

/* BM算法好后缀部分 */
int StringMatchBoyerMooreGoodSuffix(char sourceStr[],int sourceStrLength,char targetStr[],int targetStrLength) {
    int index = -1;
    // 好后缀规则
    // suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值
    int *suffix = (int *) malloc(sizeof(int) * (targetStrLength));
    for (int i = 0; i < targetStrLength; ++i) {
        suffix[i] = -1;
    }
    // 我们还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串
    int *prefix = (int *) malloc(sizeof(int) * (targetStrLength));
    for (int i = 0; i < targetStrLength; ++i) {
        prefix[i] = 0;
    }
    // 第一步：计算suffix和prefix
    // 自己的代码：中规中矩的思路
    for (int i = 1; i <= targetStrLength-1; ++i) {
        int subStrStartIndex = targetStrLength-i;
        int j = 0;
        while (j < subStrStartIndex) {
            if (targetStr[j] == targetStr[subStrStartIndex]) {
                int m = j;
                int n = subStrStartIndex;
                int k = 0;
                while (k < i) {
                    if (targetStr[m] == targetStr[n]) {
                        m++;
                        n++;
                    } else {
                        break;
                    }
                    k++;
                }
                if (k == i) {
                    suffix[i] = j;
                    if (j == 0) {
                        prefix[i] = 1;
                    }
                }
            }
            j++;
        }
    }

//    // 王铮老师的代码版本
//    /* 思路：i控制当前可以判断到的最长的子串 */
//    for (int i = 0; i < targetStrLength-1; ++i) {
//        int j = i;
//        int k = 0;
//        /* 内层循环用于看看从最短到最长子串是否有跟后缀一样长的子串一样的，k表示子串的长度，
//         * 如果发现一个字符跟从后面倒数一样的字符那么就表示有后缀一样就存数组suffix，然后继续往前看
//         * 如果此时有一个字符卡主不一样了，那么就跳出循环，往后移动一位然后再这样从后往前一个个字符和最后面的一个个字符对比 */
//        while (j >= 0 && targetStr[j] == targetStr[targetStrLength-1-k]) {
//            --j;
//            ++k;
//            suffix[k] = j+1;
//        }
//        if (j == -1) {
//            prefix[k] = 1;
//        }
//    }

    /*
    // debug
    for (int i = 0; i < targetStrLength; ++i) {
        printf("%d ",suffix[i]);
    }
    printf("\n");

    for (int i = 0; i < targetStrLength; ++i) {
        printf("%d ",prefix[i]);
    }
    printf("\n");
    //*/

    // 第二步：好后缀
    int i = 0;
    while (i <= sourceStrLength - targetStrLength) {
        int sameLength = 0;
        for (int j = targetStrLength-1; j >= 0; --j) {
            if (sourceStr[i+j] != targetStr[j]) {
                // 记录好后缀有多长
                int k = targetStrLength - 1 - j;
//                printf("好后缀的起始下标: %d \n",suffix[k]);
                if (suffix[k] == -1) {
                    // 再看看是不是有可匹配的前缀子串
                    if (prefix[k] == 1) {
                        i = i + (targetStrLength - k);
                    } else {
                        i = i + targetStrLength;
                    }
                } else {
                    i = i + (j - suffix[k] + 1);
                }
                break;
            } else {
                sameLength++;
            }
        }
        if (sameLength == targetStrLength) {
            index = i;
            break;
        }
    }

    return index;
}

/* BM算法整合:坏字符和好后缀结合使用 */
int StringMatchBoyerMoore(char sourceStr[],int sourceStrLength,char targetStr[],int targetStrLength) {
    int index = -1;
    // 坏字符规则辅助数组
    // 辅助数组(记录坏字符在模式串中出现的位置):下标是 字符的int值，值是 这个字符在模式字符串中的下标
    int *asciiArr = (int *) malloc(sizeof(int) * 256);
    for (int i = 0; i < 256; ++i) {
        asciiArr[i] = -1;
    }
    for (int i = 0; i < targetStrLength; ++i) {
        int index = (int)targetStr[i];
        asciiArr[index] = i;
    }

    // 好后缀规则辅助数组
    // suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值
    int *suffix = (int *) malloc(sizeof(int) * (targetStrLength));
    for (int i = 0; i < targetStrLength; ++i) {
        suffix[i] = -1;
    }
    // 我们还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串
    int *prefix = (int *) malloc(sizeof(int) * (targetStrLength));
    for (int i = 0; i < targetStrLength; ++i) {
        prefix[i] = 0;
    }
    // 王铮老师的代码版本
    // 思路：i控制当前可以判断到的最长的子串
    for (int i = 0; i < targetStrLength-1; ++i) {
        int j = i;
        int k = 0;
        /* 内层循环用于看看从最短到最长子串是否有跟后缀一样长的子串一样的，k表示子串的长度，
         * 如果发现一个字符跟从后面倒数一样的字符那么就表示有后缀一样就存数组suffix，然后继续往前看
         * 如果此时有一个字符卡主不一样了，那么就跳出循环，往后移动一位然后再这样从后往前一个个字符和最后面的一个个字符对比 */
        while (j >= 0 && targetStr[j] == targetStr[targetStrLength-1-k]) {
            --j;
            ++k;
            suffix[k] = j+1;
        }
        if (j == -1) {
            prefix[k] = 1;
        }
    }

    int i = 0;
    while (i <= sourceStrLength - targetStrLength) {
        int sameLength = 0;
        for (int j = targetStrLength - 1; j >= 0; --j) {
            if (targetStr[j] != sourceStr[i+j]) {
                // 坏字符需要移动的位数
                int badMoveCount = -1;
                int ci = (int)sourceStr[i+j];
                if (asciiArr[ci] != -1) {
                    // 移动 j - asciiArr[ci]
                    badMoveCount = j - asciiArr[ci];
                } else {
                    // 移动 targetStrLength
                    badMoveCount = targetStrLength;
                }

                // 好后缀需要移动的位数
                int goodMoveCount = -1;
                // 这个是关键，需要判断是否有好后缀才能使用好后缀，不然就直接使用坏字符规则了
                if (sameLength > 0) {
                    // 有好后缀
                    // 记录好后缀有多长
                    int k = targetStrLength - 1 - j;
                    if (suffix[k] == -1) {
                        // 再看看是不是有可匹配的前缀子串
                        if (prefix[k] == 1) {
                            // 有可匹配的前缀子串，这样我们可以把模式串后移 targetStrLength - k 位。
                            goodMoveCount =  (targetStrLength - k);
                        } else {
                            // 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 targetStrLength 位
                            goodMoveCount =  targetStrLength;
                        }
                    } else {
                        // 假设好后缀的长度是 k。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）
                        goodMoveCount =  (j - suffix[k] + 1);
                    }
                }
                // 坏字符和好后缀取两者中最大的移动
                i = i + (badMoveCount > goodMoveCount ? badMoveCount : goodMoveCount);
                break;

            } else {
                sameLength++;
            }
        }
        if (sameLength == targetStrLength) {
            // 找到了
            index = i;
            break;
        }
    }

    return index;
}

/* 王铮老师的代码 */
int wangzhengMoveByGS(int j,int m,int suffix[],int prefix[]) {
    int  k = m - 1 - j;
    if (suffix[k] != -1) {
        return j - suffix[k] + 1;
    }
    for (int r = j+2; r <= m-1; ++r) {
        if (prefix[m-r] == 1) {
            return r;
        }
    }
    return m;
}

/* 王铮老师的代码 */
int wangzhengBM(char sourceStr[],int sourceStrLength,char targetStr[],int targetStrLength) {
    // 坏字符规则辅助数组
    int *asciiArr = (int *) malloc(sizeof(int) * 256);
    for (int i = 0; i < 256; ++i) {
        asciiArr[i] = -1;
    }
    for (int i = 0; i < targetStrLength; ++i) {
        int index = (int)targetStr[i];
        asciiArr[index] = i;
    }
    // 好后缀规则辅助数组
    // suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值
    int *suffix = (int *) malloc(sizeof(int) * (targetStrLength));
    int *prefix = (int *) malloc(sizeof(int) * (targetStrLength));
    for (int i = 0; i < targetStrLength; ++i) {
        suffix[i] = -1;
        prefix[i] = 0;
    }
    for (int i = 0; i < targetStrLength-1; ++i) {
        int j = i;
        int k = 0;
        while (j >= 0 && targetStr[j] == targetStr[targetStrLength-1-k]) {
            --j;
            ++k;
            suffix[k] = j+1;
        }
        if (j == -1) {
            prefix[k] = 1;
        }
    }
    // 核心
    int i = 0;
    while (i <= sourceStrLength-targetStrLength) {
        int j;
        for (j = targetStrLength-1; j >= 0; --j) {
            if (sourceStr[i+j] != targetStr[j]) {
                break;
            }
        }
        if (j < 0) {
            return i;
        }
        int x = j - asciiArr[(int)sourceStr[i+j]];
        int y = 0;
        if (j < targetStrLength-1) {
            y = wangzhengMoveByGS(j,targetStrLength,suffix,prefix);
        }
        i = i + (x > y ? x : y);
    }
    return -1;
}

/* KMP算法:
 * https://www.cnblogs.com/dusf/p/kmp.html
 * https://www.cnblogs.com/tangzhengyue/p/4315393.html */
int StringMatchKMP(char sourceStr[],int sourceStrLength,char targetStr[],int targetStrLength) {
    // next数组存模式串和主串不匹配时模式串的下标j(0 <= j < targetStrLength) ,next[0] = -1,-1表示移动主串i
    // 求解next数组的思想是数学归纳法，即动态规划，已知next[i]求next[i+1],有点递归的思想
    int *next = (int *) malloc(sizeof(int) * targetStrLength);
    int j = 0;
    int k = -1;
    next[0] = -1;
    while (j < targetStrLength - 1) {
        // 这个递归的关键是利用上一次的结果来求，最后缩小到next[0]或者next[1]的时候，说明此时j的下一个next[j+1]的k值绝不会是大于next[j]很多的，最多就k+1，
        // 所以一旦你的next[j]回到next[0]的情况，那么你的next[j+1]最多也就k+1,所以此时你的k是要重新赋值0的，因为next[0]在外部是固定-1了
        if (k == -1) {
            next[j+1] = 0;
            k = 0; // 因为next[0]在外部是固定-1了所以有可能这个k又变成-1了，这里为了修复下面那个k = next[k] = -1的可能情况
            j++;
            continue;
        }
        if (targetStr[k] == targetStr[j]) {
            if (targetStr[k+1] == targetStr[j+1]) {
                next[j+1] = next[k+1];
            } else {
                next[j+1] = k + 1;
            }
            k++;
            j++;
        } else {
            k = next[k]; // 因为next[0]在外部是固定-1了所以有可能这个k又变成-1了
        }
    }

    // debug
    for (int i = 0; i < targetStrLength; ++i) {
        printf("%d ",next[i]);
    }
    printf("\n");

    int i = 0;
    j = 0;
    while (i <= sourceStrLength - 1) {
        if (sourceStr[i] == targetStr[j]) {
            if (j == targetStrLength - 1) {
                return i-j;
            }
            i++;
            j++;
        } else {
            if (next[j] != -1) {
                j = next[j];
            } else {
                j = 0;
                i++;
            }
        }
    }
    return -1;

}


/* 字符串匹配demo */
void StringMatchDemo() {

    printf("--------------------------- 字符串匹配 ------------------------\n");

    {
        char source[] = {'b','a','d','d','d','e','f'};
        char target[] = {'d','d','e'};
        int index = StringMatchBruteForce(source, sizeof(source)/sizeof(char),target,sizeof(target)/sizeof(char));
        printf("暴力匹配算法匹配到的起始下标: %d\n",index);
    }

    {
        char source[] = {'a','a','a','a','a','a','a'};
        char target[] = {'b','a','a','a'};
        int index = StringMatchBoyerMooreBadCharacter(source, sizeof(source)/sizeof(char),target,sizeof(target)/sizeof(char));
        printf("BM算法坏字符匹配到的起始下标: %d\n",index);
    }

    {
        char source[] = {'b','a','d','d','d','e','f'};
        char target[] = {'d','d','e'};
        int index = StringMatchBoyerMooreGoodSuffix(source, sizeof(source)/sizeof(char),target,sizeof(target)/sizeof(char));
        printf("BM算法好后缀匹配到的起始下标: %d\n",index);
    }

    {
        char source[] = {'a','a','a','a','a','a','a'};
        char target[] = {'b','a','a','a'};
        int index = StringMatchBoyerMoore(source, sizeof(source)/sizeof(char),target,sizeof(target)/sizeof(char));
        printf("BM算法匹配到的起始下标: %d\n",index);
    }

    {
        char *s = "abcacabdc";
        char *t = "abd";
        int index = StringMatchBoyerMoore(s, StringLength(s),t, StringLength(t));
        printf("BM算法匹配到的起始下标: %d\n",index);
    }

    {
        char *s = "abcacabdc";
        char *t = "abd";
        int index = wangzhengBM(s, StringLength(s),t, StringLength(t));
        printf("王铮匹配到的起始下标: %d\n",index);
    }

    {
        char source[] = {'a','a','a','a','a','a','a'};
        char target[] = {'b','a','a','a'};
        int index = StringMatchBoyerMoore(source, sizeof(source)/sizeof(char),target,sizeof(target)/sizeof(char));
        printf("BM算法匹配到的起始下标: %d\n",index);
    }

    {
        char *s = "badddef";
        char *t = "de";
        int index = StringMatchKMP(s, StringLength(s),t, StringLength(t));
        printf("KMP算法匹配到的起始下标: %d\n",index);
    }

    {
        char *s = "算法匹配到的";
        int l = StringLength(s);
        printf("%d\n",l);
        char *t = "配到";
        int index = StringMatchKMP(s, StringLength(s),t, StringLength(t));
        printf("KMP算法匹配到的起始下标: %d\n",index);
    }


}